Integrated circuit devices, commonly known as chips, continue to become more powerful and complex as semiconductor manufacturing technologies have advanced. Whereas early integrated circuit devices included fewer than one hundred transistors, it is now common to integrate hundreds of millions of transistors into a single integrated circuit device. This increased transistor count enables some operations that once required several integrated circuit devices to now be implemented in a single integrated circuit device, often providing greater performance at a lower cost. For example, where previously a data processing system might require separate integrated circuit devices for a microprocessor, a memory, a bus interface, and a memory controller, advances in chip density now permit all of these functions to be integrated into the same integrated circuit device. Such devices are typically known as “systems on a chip” due to the high level of integration they provide.
Increases in chip density have also significantly affected the design methodologies used for integrated circuit chips. Rather than manually laying out individual transistors or logic gates in a design to obtain a desired logic function, typically the functional aspects of the design process are separated from the physical aspects. The functional aspects of a design are typically addressed via a process known as a logic design, which results in the generation of a functional definition of a circuit design, typically defined in a hardware description language (HDL) such as VHDL or Verilog. An HDL representation of a circuit is analogous in many respects to a software program, as the HDL representation generally defines the logic or functions to be performed by a circuit design. Moreover, by separating logic design from physical layout, functions are capable of being defined at a higher level of abstraction. Many design methodologies rely on the concept of hierarchical logic design, where circuits are defined in units and grouped together in one or more parent containers representing collections of units performing higher level functions.
In parallel with the creation of the HDL representation, a physical definition of a circuit design is created typically via a layout process, often referred to as integration, to essentially create a “floor plan” of logic gates and interconnects between the logic gates representing the actual physical arrangement of circuit elements on the manufactured integrated circuit. Automation tools have been developed to utilize predefined cells or blocks of complete circuits to assist with the layout, thus eliminating the need to work with millions of individual logic gates. For example, synthesis tools have been developed to generate Random Logic Macro (RLM) blocks from an HDL representation of a design, whereby an individual laying out a design is merely required to place the RLM blocks and connect them to one another to complete the circuit design. In addition, some designs incorporate blocks from off-the-shelf (OTS) logic blocks, which are reusable from design to design.
Once a physical definition is created, testing and simulation of the design may be performed to identify any potential timing and/or manufacturability issues, and once the design has been determined to meet these requirements, the design may be utilized to manufacture integrated circuits.
One manner of improving the performance of the tools used to design integrated circuit devices is to rely on parallelization to leverage the computing power of multiple processors and/or computer systems.
For example, one class of tools conventionally used in integrated circuit design are logic and physical synthesis tools. Synthesis is the process of transforming an input net list (a set of components interconnected by a set of wires) of a design into an optimized net list under certain desired optimization criteria. Physical synthesis additionally involves the task of mapping the components of the net list to a physical image to realize the design. Optimizations involved in physical synthesis typically consist of several complex steps and need to meet several constraints while achieving desired goals. It has been found that in many cases the physical mapping as well as the logical transformations are best dealt with simultaneously in order to achieve best results, a concept sometimes referred to as Placement Driven Synthesis (PDS). This problem space for PDS is usually very large leading to very long run times, so a significant need exists for reducing the run times of PDS and other logical and/or physical synthesis tools.
Conventional parallelization techniques in connection with integrated circuit design usually involve partitioning a problem into fairly independent sub-problems and processing each of them separately. These solutions of these sub-problems are then merged to obtain a solution for the original problem. However, while there are many problems that lend themselves to such partitioning it has been found that it is often difficult to partition the problem of physical and logical synthesis either logically or physically, which renders the task of parallelization even more difficult. This is because any PDS change made to the design can affect much of the rest of the entire design, or at least it is difficult if not impossible to tell a priori what effect a PDS change will have on other parts of the design.
Therefore, a significant need exists for an improved manner of parallelizing physical and logical synthesis operations to reduce runtime.